package com.mc.string;
public class LCS {
	private static String string1;
	private static String string2;
	
	public static void LCS(String str1,String str2){
		string1 = str1;
		string2 = str2;
		int[][] mat = new int[str1.length()+1][str2.length()+1];
		int[][] flag = new int[str1.length()+1][str2.length()+1];
		
		for(int i=0;i<flag.length;i++)
			for(int j=0;j<flag[0].length;j++)
				flag[i][j] = 0;
		
		for(int i=0;i<str1.length()+1;i++)
			mat[i][0]=0;
		for(int i=0;i<str2.length()+1;i++)
			mat[0][i]=0;
		
		for(int i=1;i<=str1.length();i++){
			for(int j=1;j<=str2.length();j++){
				if(str1.charAt(i-1)==str2.charAt(j-1))
				{
					mat[i][j]=mat[i-1][j-1]+1;
					flag[i][j]=1;
				}
				else if(mat[i-1][j]>mat[i][j-1]){
					mat[i][j]=mat[i-1][j];
					flag[i][j]=2;
				}
				else{
					mat[i][j]=mat[i][j-1];
					flag[i][j]=3;
				}
			}
		}
		System.out.println(mat[str1.length()][str2.length()]);
		print(flag,str1.length(),str2.length());
	}
	private static void print(int[][] flag,int i,int j){
		if(i==0||j==0)
			return;
		if(flag[i][j]==1){
			System.out.println(string2.charAt(j-1));
			print(flag, i-1, j-1);
		}
		else{
			if(flag[i][j]==2)
				print(flag,i-1,j);
			else
				print(flag,i,j-1);
		}
			
		
	}
	public static void main(String[] args) {
		LCS.LCS("abcde", "bcccc");
	}
}
